sega_genesis_graphic_compression_formatsfandomcom-20200213-history
Example of Nemesis Compression
Here is an example of how to compress graphics using Nemesis compression. Example Tiles Say, for example, you wanted to compress this 3-tile set. These are the numerals 1-3 in the classic NES font. The tiles are magnified 4x so you see the detail. For this example, say that the blue pixels are color 0 and the yellow pixels are color 1. Analyzing Runs The first row of the first tile has pixel values 00011000, which is grouped as follows: 0x3, 1x2, 0x3. For the first tile, you get the following runs: 00011000 = 0x3, 1x2, 0x3 00111000 = 0x2, 1x3, 0x3 00011000 = 0x3, 1x2, 0x3 00011000 = 0x3, 1x2, 0x3 00011000 = 0x3, 1x2, 0x3 00011000 = 0x3, 1x2, 0x3 01111110 = 0x1, 1x6, 0x1 00000000 = 0x8 For the second tile: 01111100 = 0x1, 1x5, 0x2 11000110 = 1x2, 0x3, 1x2, 0x1 00001110 = 0x4, 1x3, 0x1 00111100 = 0x2, 1x4, 0x2 01111000 = 0x1, 1x4, 0x3 11100000 = 1x3, 0x5 11111110 = 1x7, 0x1 00000000 = 0x8 For the third tile: 01111110 = 0x1, 1x6, 0x1 00001100 = 0x4, 1x2, 0x2 00011000 = 0x3, 1x2, 0x3 00111100 = 0x2, 1x4, 0x2 00000110 = 0x5, 1x2, 0x1 11000110 = 1x2, 0x3, 1x2, 0x1 01111100 = 0x1, 1x5, 0x2 00000000 = 0x8 Combining Runs, row-to-row Sometimes, the last run of a row and the first run of the next row can be combined. This happens when the pixel values in these runs are the same. 'Tile 1' The first tile is expressed as: 0x3, 1x2, 0x3, 0x2, 1x3, 0x3, 0x3, 1x2, 0x3, 0x3, 1x2, 0x3, 0x3, 1x2, 0x3, 0x3, 1x2, 0x3, 0x1, 1x6, 0x1, 0x8 Similar runs could then be combined as follows: 0x3, 1x2, 0x5, 1x3, 0x6, 1x2, 0x6, 1x2, 0x6, 1x2, 0x6, 1x2, 0x4, 1x6, 0x8, 0x1 Note that runs cannot contain more than 8 bits. 'Tile 2' 0x1, 1x5, 0x2, 1x2, 0x3, 1x2, 0x1, 0x4, 1x3, 0x1, 0x2, 1x4, 0x2, 0x1, 1x4, 0x3, 1x3, 0x5, 1x7, 0x1, 0x8 Becomes: 0x1, 1x5, 0x2, 1x2, 0x3, 1x2, 0x5, 1x3, 0x3, 1x4, 0x3, 1x4, 0x3, 1x3, 0x5, 1x7, 0x8, 0x1 'Tile 3' 0x1, 1x6, 0x1, 0x4, 1x2, 0x2, 0x3, 1x2, 0x3, 0x2, 1x4, 0x2, 0x5, 1x2, 0x1, 1x2, 0x3, 1x2, 0x1, 0x1, 1x5, 0x2, 0x8 Becomes: 0x1, 1x6, 0x5, 1x2, 0x5, 1x2, 0x5, 1x4, 0x7, 1x2, 0x1, 1x2, 0x3, 1x2, 0x2, 1x5, 0x8, 0x2 Combining Runs, tile-to-tile Here is the entire set: 0x3, 1x2, 0x5, 1x3, 0x6, 1x2, 0x6, 1x2, 0x6, 1x2, 0x6, 1x2, 0x4, 1x6, 0x8, 0x1 0x1, 1x5, 0x2, 1x2, 0x3, 1x2, 0x5, 1x3, 0x3, 1x4, 0x3, 1x4, 0x3, 1x3, 0x5, 1x7, 0x8, 0x1 0x1, 1x6, 0x5, 1x2, 0x5, 1x2, 0x5, 1x4, 0x7, 1x2, 0x1, 1x2, 0x3, 1x2, 0x2, 1x5, 0x8, 0x2 It can be further improved like so: 0x3, 1x2, 0x5, 1x3, 0x6, 1x2, 0x6, 1x2, 0x6, 1x2, 0x6, 1x2, 0x4, 1x6, 0x8, 0x2 1x5, 0x2, 1x2, 0x3, 1x2, 0x5, 1x3, 0x3, 1x4, 0x3, 1x4, 0x3, 1x3, 0x5, 1x7, 0x8, 0x2 1x6, 0x5, 1x2, 0x5, 1x2, 0x5, 1x4, 0x7, 1x2, 0x1, 1x2, 0x3, 1x2, 0x2, 1x5, 0x8, 0x2 This makes our final data. Counting Runs Using the optimized data above, here is a count of our pixel runs. These runs are sorted in order from the least common to the most common: We can see that 1x2 is the most common run, with 12 occurrences, and there are four runs tied for the least number of occurrences. Building a Huffman Tree Next, the frequency counts above are transformed into a Huffman tree. Consider the tree in the form of a table. So far, it looks like this: To create a new node, take the two nodes with the least frequency, add their counts together, then make a new node with that count. In this example, the two least-frequency nodes are 1 and 2. Their counts are both 1, so the combined count is 2. Node 15 has a count of 2; its left child is node 1, and its right child is node 2. Then, remove nodes 1 and 2 from the list, and add node 15. Continue in this manner until only one node is left. That is the root. When finished, the table looks like this: Once the tree has been constructed, we can begin to figure out the codes for each of our runs.